#include<bits/stdc++.h>
//#define int long long
using namespace std;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-') f=-1;ch=getchar();}
    while(isdigit(ch)) x=x*10+(ch^48),ch=getchar();
    return x*f;
}
inline void write(int x)
{
    if(!x)
        putchar('0');
    char F[200];
    int tmp=x>0?x:-x;
    if(x<0)
        putchar('-');
    int cnt=0;
    while(tmp>0)
        F[cnt++]=tmp%10+'0',tmp/=10;
    while(cnt>0)
        putchar(F[--cnt]);
}
const int maxn=5e5+10;
map<pair<int,int>,bool> mp;
int n,m,k,r;
int scc[maxn],c;
int f[maxn],dep[maxn],sz[maxn];
int idx;
int dfn[maxn],pre[maxn],son[maxn],top[maxn];
int t[maxn];
struct node
{
	int cnt,head[maxn],nxt[maxn<<1],to[maxn<<1];
	inline void add(int u,int v)
	{
		nxt[++cnt]=head[u];
		head[u]=cnt;
		to[cnt]=v;
	}
}g,gg;
inline int lowbit(int x)
{
	return x&(-x);
}
namespace tarjan
{
	int dfn[maxn],low[maxn];
	int t,brg[maxn<<1];
	void dfs(int u,int ine)
	{
		dfn[u]=low[u]=++t;
		for(int i=g.head[u];i;i=g.nxt[i])
		{
			if(i==ine) 
				continue;
			int v=g.to[i];
			if(dfn[v]==0)
			{
				dfs(v,i^1);
				low[u]=min(low[u],low[v]);
				if(low[v]>dfn[u]) 
					brg[i]=brg[i^1]=1;
			}
			else 
				low[u]=min(low[u],dfn[v]);
		}
	}
	bool vis[maxn];
	void dfs(int u)
	{
		scc[u]=c,vis[u]=1;
		for(int i=g.head[u];i;i=g.nxt[i])
		{
			if(brg[i]) 
				continue;
			int v=g.to[i];
			if(!vis[v]) 
				dfs(v);
		}
	}
	void main()
	{
		dfs(1,0);
		for(int i=1;i<=n;i++)
		{
			if(!vis[i])
			{
				c++;
				dfs(i);
			}			
		}
	}
}
inline void dfs1(int u,int fa)
{
	f[u]=fa,dep[u]=dep[fa]+1,sz[u]=1;
	for(int i=g.head[u];i;i=g.nxt[i])
	{
		int v=g.to[i];
		if(v==fa) 
			continue;
		dfs1(v,u);
		sz[u]+=sz[v];
		if(sz[son[u]]<sz[v]||son[u]==0) 
			son[u]=v;
	}
	return;
}
inline void dfs2(int u,int tp)
{
	dfn[u]=++idx;
	top[u]=tp;
	pre[idx]=u;
	if(son[u]==0) 
		return;
	dfs2(son[u],tp);
	for(int i=g.head[u];i;i=g.nxt[i])
	{
		int v=g.to[i];
		if(v==f[u]||v==son[u]) 
			continue;
		dfs2(v,v);
	}
	return;
}
inline void add(int x,int v)
{
	for(;x<=c;x+=lowbit(x))
		t[x]+=v;
	return;
}
inline int query(int x)
{
	int res=0;
	for(;x;x-=lowbit(x))
		res+=t[x];
	return res;
}
inline void change(int x,int y)
{
	add(x,1);
	add(y+1,-1);
	return;
}
inline void changetree(int x,int y)
{
	while(top[x]!=top[y])
	{
		if(dep[top[x]]<dep[top[y]]) swap(x,y);
		change(dfn[top[x]],dfn[x]),x=f[top[x]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	change(dfn[x]+1,dfn[y]);
}
signed main()
{
	freopen("hide.in","r",stdin);
	freopen("hide.out","w",stdout);
	cin>>n>>m>>k>>r;
	g.cnt=gg.cnt=1;
	for(int i=1,u,v;i<=m;i++)
	{
		cin>>u>>v;
		g.add(u,v);
		g.add(v,u);
	}
	tarjan::main();
	for(int j=1;j<=n;j++)
	{
		for(int i=g.head[j];i;i=g.nxt[i])
		{
			int v=g.to[i];
			if(scc[j]!=scc[v]&&!mp[{scc[j],scc[v]}])
			{
				gg.add(scc[j],scc[v]);
				gg.add(scc[v],scc[j]);
				mp[{scc[j],scc[v]}]=mp[{scc[v],scc[j]}]=1;
			}
		}		
	}
	g=gg;
	dfs1(1,0);
	dfs2(1,1);
	for(int i=1,u,v;i<=k;i++)
	{
		cin>>u>>v;
		u=scc[u];
		v=scc[v];
		if(u!=v) 
			changetree(u,v);
	}
	priority_queue<int> q;
	for(int i=1;i<=c;i++)
		q.push(query(dfn[i]));
	int ans=0;
	while(r--)
	{
		if(q.empty()) 
			break;
		ans+=q.top();
		q.pop();
	}
	cout<<ans<<'\n';
	return 0;
}

